1. Field of the Invention
This invention relates to computer memory management systems and, more particularly, to method and apparatus for translating virtual addresses to physical addresses in computer memory systems which utilize virtual memory addressing.
2. History of the Prior Art
A virtual memory system is one which allows addressing of very large amounts of memory as though all of that memory were the main memory of the computer system. Such a system allows this even though actual main memory may consist of some substantially lesser amount of storage space than the addressable memory. For example, main memory may consist of one megabyte of random access memory while sixty-four megabytes of memory are addressable using the virtual memory addressing system.
Virtual memory systems accomplish this feat by providing memory management units which translate virtual memory addresses into physical memory addresses. A particular physical address may be in main memory or in long term storage. If the physical address of information sought is in main memory, the information is accessed and utilized by the computer. If the physical address is in long term storage, the information is transferred (usually in a block referred to as a page) to main memory where it may be used. This transfer may necessitate that other information be swapped out of main memory to long term memory to make room for the new information. If so, this is accomplished under control of the memory management unit.
Although a computer may have a very large addressable space because of its virtual memory system, this does not guarantee that the computer will operate rapidly. Rapid operation is determined by how rapidly the components operate and how fast memory may be accessed. The latter depends upon the speed of the components, but to a greater extent upon the process required to translate addresses from virtual to physical and then retrieve the information from memory. A basic virtual memory arrangement creates lookup tables which are stored in main memory. Any virtual address presented to the memory management unit is compared to the values stored in these tables to determine the physical address to access. There are often several levels of tables, and the comparison takes a great deal of system clock time.
To overcome this delay, virtual memory systems often include cache memories which use very fast components to store recently used data and instructions. These cache memories are usually connected so that they are rapidly accessible to the processors. These caches are first looked to by a processor before going to main memory for any information. The theory of these caches is that information most recently used is more likely to be needed again before other information is needed. This theory is valid, and many systems using cache memories have hit rates of over ninety percent.
However, even these cache memories must be addressed in some manner, either directly using the virtual addresses or through translated physical addresses. Addressing by virtual addresses raises a substantial problem involving multiple copies of information, some of which may be stale and unusable; this problem is expensive to overcome. Consequently, cache addressing by physical addresses is preferred for its economy. Since this form of addressing requires that the virtual address be translated to a physical address before the cache memory can be accessed, systems using these cache memories have developed arrangements for quickly providing the physical addresses without having to go through all of the steps of the page table lookup process.
A typical arrangement of this type is called a translation lookaside buffer (TLB). A translation lookaside buffer is essentially a buffer for caching virtual addresses which have been recently used along with their related physical addresses. Such an address cache works on the same principle as do caches holding data and instructions, the most recently used addresses are more likely to be used than are other addresses. When provided a virtual address which is held in the translation lookaside buffer, the translation lookaside buffer furnishes a physical address for the information. If that physical address is in the related cache, then the information is immediately available to the processor without the necessity of going through the time consuming process of referring to the page lookup tables in main memory.
If when the processor sends a virtual address to the translation lookaside buffer, the address is not included in the translation lookaside buffer, then the memory management unit must retrieve the address using the lookup tables in main memory. To accomplish this, the typical memory management unit looks to a register for the address of a base table which usually stores addresses pointing to other levels of tables. At the base table the memory management unit retrieves this pointer and places it in another register. The memory management unit uses this pointer to go to the next level of table. This process continues until the physical address of the information sought is recovered. When the physical address is recovered, it is stored along with the virtual address in the translation lookaside buffer so that the next time it is needed it is immediately available. When the information is recovered, it is stored in the cache under the physical address. This saves a great deal of time on the next use of the information because a typical lookup in the page tables may take from ten to fifteen clock cycles at each level of the search, while accessing the information using the translation lookaside buffer and the caches may require only one or two clock cycles.
One of the difficulties with such a system is that the page table lookup process is required whenever a physical address is not in the translation lookaside buffer. This is true even though most of the steps of that lookup (the deriving of pointers) have occurred over and over prior to the particular lookup operation. This occurs because the registers used to store pointers to the different levels of page tables are in a resource apart from the translation lookaside buffer and are typically capable of storing only one address pointer at a time. Consequently, once a lookup process begins, it is necessary to step through the entire process for each level of the table which must be traversed; that is, the machine must find a first pointer and store it, use that pointer to find the next pointer and store it, and then use that pointer (hopefully) to find the address. With the next lookup process, all of these pointers are written over. In economical prior art arrangements without a separate cache for storing address pointers, there is no way to short circuit this time consuming process.
Not only is the constant referral from the translation lookaside buffer to page tables a problem, many addresses which must be translated are simply not stored in the translation lookaside buffer at all. For example, in addition to data and instructions, a processor often deals with input/output information. Although this information may be used by the processor, it is usually handled by separate addressing means such as an input/output processor or a direct memory access unit.
Thus, very fast prior art computer systems using separate caches for data and for instructions and having a direct memory access facility, typically require individual memory management resources for accomplishing the functions of a translation lookaside buffer to provide addressing within the caches, for doing the lookups in the page tables of main memory, and for managing the addressing of input/output information. In prior art systems a very large amount of silicon was required for these different individual arrangements for rapidly addressing data, instructions, and input/output functions. Moreover, prior art systems are incapable of providing the speed of address translation desired in a substantial number of situations.